# 98.验证二叉搜索树
# 给你一个二叉树的根节点root ，判断其是否是一个有效的二叉搜索树。
#
# 有效二叉搜索树定义如下：
# 节点的左子树只包含小于当前节点的数。
# 节点的右子树只包含大于当前节点的数。
# 所有左子树和右子树自身必须也是二叉搜索树。
#
# 示例1：
# 输入：root = [2, 1, 3]
# 输出：true
#
# 示例2：
# 输入：root = [5, 1, 4, null, null, 3, 6]
# 输出：false
# 解释：根节点的值是5 ，但是右子节点的值是4


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def isValidBST(self, root: [TreeNode]) -> bool:
        # 没看视频的情况下， 基础思路是对的，就是要看中序遍历，二叉搜索树的中序遍历应该从小到大的
        # 然后我这里是把他和sort后对比，看是否一样，注意，这里复制要用[:],不然二者指向一个列表
        # 不过我漏了一个东西，即列表里不能有相同元素
        # 参考答案的比较是for循环列表，从下标1开始，如果后者小于等于前者，则返回False
        def inorder(root):
            res = []
            def dfs(root):
                if not root:
                    return
                dfs(root.left)
                res.append(root.val)
                dfs(root.right)
            dfs(root)
            return res
        inner = inorder(root)
        tmp = []
        for i in inner:
            if i not in tmp:
                tmp.append(i)
            else:
                return False
        cp_inner = inner[:]
        inner.sort()
        if cp_inner == inner:
            return True
        else:
            return False

    #还有其他很多中解法，我先挂一下，之后再看

    def isValidBST1(self, root: TreeNode) -> bool:
        # 规律: BST的中序遍历节点数值是从小到大.
        cur_max = -float("INF")

        def __isValidBST(root: TreeNode) -> bool:
            nonlocal cur_max

            if not root:
                return True

            is_left_valid = __isValidBST(root.left)
            if cur_max < root.val:
                cur_max = root.val
            else:
                return False
            is_right_valid = __isValidBST(root.right)

            return is_left_valid and is_right_valid

        return __isValidBST(root)


    def isValidBST3(self, root: TreeNode) -> bool: # 迭代-中序遍历
        stack = []
        cur = root
        pre = None
        while cur or stack:
            if cur: # 指针来访问节点，访问到最底层
                stack.append(cur)
                cur = cur.left
            else: # 逐一处理节点
                cur = stack.pop()
                if pre and cur.val <= pre.val: # 比较当前节点和前节点的值的大小
                    return False
                pre = cur
                cur = cur.right
        return True

    def isValidBST4(self, root: TreeNode) -> bool: #
        # method 2
        que, pre = [], None
        while root or que:
            while root:
                que.append(root)
                root = root.left
            root = que.pop()
            # 对第一个节点只做记录，对后面的节点进行比较
            if pre is None:
                pre = root.val
            else:
                if pre >= root.val: return False
                pre = root.val
            root = root.right
        return True

if __name__ == '__main__':
    a31 = TreeNode(1)
    a32 = TreeNode(3)
    a21 = TreeNode(2,a31,a32)
    a22 = TreeNode(7)
    a11 = TreeNode(4,a21,a22)
    tmp = Solution()
    res = tmp.isValidBST(a11)
    print(res)